package com.camus.verify.algorithm.impl;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.camus.utils.BigDecimalUtils;
import com.camus.verify.algorithm.MatchTarget;
import com.camus.verify.algorithm.SubsetAlgorithm4BigDecimal;

/**
 * 递归优化(有大量重复元素的场景)算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfDistinctRecursion4BigDecimal implements SubsetAlgorithm4BigDecimal {

	@Override
	public MatchTarget[] findSubsetWithinRange(MatchTarget[] candidateArr, BigDecimal lower, BigDecimal upper) {
		// 消重，记录重复元素的索引
		// K=num V=index
		Map<BigDecimal, List<Integer>> indexListMap = new HashMap<>();
		for (int i = 0; i < candidateArr.length; i++) {
			List<Integer> indexList = indexListMap.get(candidateArr[i].getTarget());
			if (indexList == null) {
				indexList = new ArrayList<>();
				indexListMap.put(candidateArr[i].getTarget(), indexList);
			}
			indexList.add(i);
		}

		// 准备消重后的numArr
		int distinctItemSize = indexListMap.keySet().size();
		BigDecimal[] distinctItemArr = new BigDecimal[distinctItemSize];
		for (BigDecimal distinctItem : indexListMap.keySet()) {
			distinctItemArr[--distinctItemSize] = distinctItem;
		}

		// 逐层递归
		MatchTarget[] subsetArr = findSubsetWithinRange(candidateArr, lower, upper, new boolean[candidateArr.length],
				distinctItemArr, 0, indexListMap, BigDecimal.ZERO);

		return subsetArr == null || subsetArr.length == 0 ? null : subsetArr;

	}

	/**
	 * 
	 * @param candidateArr
	 * @param lower
	 * @param upper
	 * @param flagArr
	 * @param distinctItemArr
	 * @param nextIdx
	 * @param indexListMap
	 * @param curSum
	 * @return
	 */
	public MatchTarget[] findSubsetWithinRange(MatchTarget[] candidateArr, BigDecimal lower, BigDecimal upper,
			boolean[] flagArr, BigDecimal[] distinctItemArr, int nextIdx, Map<BigDecimal, List<Integer>> indexListMap,
			BigDecimal curSum) {
		SubsetAlgorithm4BigDecimal.counter.get().getAndIncrement();
		// 递归终止条件
		if (BigDecimalUtils.isWithinRange(curSum, upper, lower) == 0) {
			return filterSubset(candidateArr, flagArr);
		}
		if (nextIdx >= distinctItemArr.length) {
			return null;
		}

		// 处理当前层逻辑
		BigDecimal distinctItem = distinctItemArr[nextIdx];
		List<Integer> idxList = indexListMap.get(distinctItem);
		// 对于本层的distinctItem，有idxList.size()+1种选择：
		// 1.包含0个distinctItem 2.包含1个distinctItem...n.包含所有的distinctItem
		for (int size = 0; size <= idxList.size(); size++) {
			// process current logic
			for (int i = 0; i < size; i++) {
				flagArr[idxList.get(i)] = true;
			}

			// drill down
			MatchTarget[] result = findSubsetWithinRange(candidateArr, lower, upper, flagArr, distinctItemArr,
					nextIdx + 1, indexListMap, curSum.add(distinctItem.multiply(new BigDecimal(size))));
			if (result != null) {
				return result;
			}

			// restore current status
			for (int i = 0; i < size; i++) {
				flagArr[idxList.get(i)] = false;
			}
		}
		return null;
	}

	private MatchTarget[] filterSubset(MatchTarget[] candidateArr, boolean[] flagArr) {
		int len = candidateArr.length;

		int size = 0;
		for (int i = 0; i < len; i++) {
			if (flagArr[i]) {
				size++;
			}
		}

		MatchTarget[] subsetArr = new MatchTarget[size];
		for (int i = len - 1; i >= 0; i--) {
			if (flagArr[i]) {
				subsetArr[--size] = candidateArr[i];
			}
		}
		return subsetArr;
	}

}
